package ch3.part4;

import java.util.Arrays;

/**
 * 最大优先队列，内部基于最大堆实现。
 * 包含出队，入队，上浮，下沉，数组扩容等方法
 *
 * @author liuwanxiang
 * @version 2019/05/17
 */
public class PriorityQueue {

    private int[] array;
    private int size;

    public PriorityQueue() {
        this.array = new int[32];
    }

    /**
     * 入队列
     * 时间复杂度：O(n) = log^n
     *
     * @param data 队列中元素
     */
    public void in(int data) {
        if (size >= array.length) {
            resize();
        }
        array[size++] = data;
        upAdjust();
    }

    /**
     * 新插入的最末节点上浮
     */
    private void upAdjust() {
        int childIndex = size - 1;
        int parentIndex = (childIndex - 1) / 2;
        int tempData = array[childIndex];
        while (childIndex > 0 && tempData > array[parentIndex]) {
            array[childIndex] = array[parentIndex];
            childIndex = parentIndex;
            parentIndex = (childIndex - 1) / 2;
        }
        array[childIndex] = tempData;
    }

    /**
     * 出队列
     * 时间复杂度：O(n) = log^n
     *
     * @return data
     */
    public int out() {
        if (size <= 0) {
            throw new RuntimeException("Empty Queue~");
        }
        int rst = array[0];
        array[0] = array[--size];
        downAdjust();
        return rst;
    }

    /**
     * 堆顶下沉
     */
    private void downAdjust() {
        int tempData = array[0];
        int parentIndex = 0;
        int childIndex = parentIndex * 2 + 1;

        while (childIndex < size) {
            if (childIndex + 1 < size && array[childIndex + 1] > array[childIndex]) {
                childIndex++;
            }
            if (tempData > array[childIndex]) {
                break;
            }
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = parentIndex * 2 + 1;
        }
        array[parentIndex] = tempData;
    }

    /**
     * 队列扩容，容量翻倍
     */
    private void resize() {
        array = Arrays.copyOf(array, array.length * 2);
    }

    public static void main(String[] args) {

        PriorityQueue queue = new PriorityQueue();
        queue.in(10);
        queue.in(30);
        queue.in(20);
        queue.in(40);
        queue.in(50);

        System.out.println(queue.out());
        System.out.println(queue.out());
        System.out.println(queue.out());
        System.out.println(queue.out());

        queue.in(60);

        System.out.println(queue);
    }
}
